# 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "bcabc"
# 输出："abc"
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "cbacdcbc"
# 输出："acdb" 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 1000 
#  s 由小写英文字母组成 
#  
# 
#  
# 
#  注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同 
# 
#  Related Topics 栈 贪心 字符串 单调栈 👍 222 👎 0
from collections import defaultdict


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def smallestSubsequence(self, s: str) -> str:
        d = defaultdict(int)
        stack = []
        s_set = set()
        for i in s:
            d[i] = d.get(i, 0) + 1

        for i in s:
            if i not in s_set:
                while stack and i <= stack[-1] and d[stack[-1]] > 1:
                    p = stack.pop()
                    s_set.remove(p)
                    d[p] -= 1
                stack.append(i)
                s_set.add(i)
            else:
                d[i] -= 1

        return ''.join(stack)


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().smallestSubsequence(s="cbacdcbc"))
